import java.util.Arrays;

/**
 * 16.最接近的三数之和
 */
public class Exerciser2 {
    public int threeSumClosest(int[] nums, int target) {
        // 排序 + 双指针
        Arrays.sort(nums);
        // 将其排成增序
        int ret = nums[0] + nums[1] + nums[2]; // 对返回值进行初始化，整个数组中三个最小的值之和，nums中最少都存在3个数
        // 因为是求 三数之和，那么可以 定一找二 利用 对撞双指针的方式，找另外的两个值，
        // 因为是严格递增的数组，那么这样的方式可以控制 三数子和的大小
        for(int i = 0;i < nums.length;i++) {
            // 定一
            int left = i + 1,right = nums.length - 1;
            while(left < right) {
                // 因为要找两个数，所以这里不能相等
                int sum = nums[i] + nums[left] + nums[right];
                if(Math.abs(target - sum) < Math.abs(target - ret)) {
                    // 说明sum这个和是距离target近的，越近 三数之和 和 target 之间的距离的绝对值就越小
                    // 这样就需要更新返回值
                    ret = sum;
                }
                if(sum > target) {
                    // 三数之和大于target的话，把right往左移，那么三数之和就会减小，更加接近target
                    right--;
                }else if(sum < target) {
                    // 三数之和小于target的话，把left往右移，那么三数之和就会增大，更加接近target
                    left++;
                }else {
                    // 三数之和 和 target相等，那么直接返回这个和
                    return ret;
                }
            }
        }
        // 全部判断结束之后，因为必有一个解，那么直接返回ret
        return ret;
    }
}
